package com.lee.algorithm.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/***
 * @description: 打印一个字符串的全部子序列，包括空字符串
 * @author : 青石路
 * @date: 2021/12/24 21:03
 */
public class PrintAllSubsquences {

    public static void main(String[] args) {
        printAllSubsquence("abc");
    }

    public static void printAllSubsquence(String str) {
        char[] chs = str.toCharArray();
        choiceIndexChar(chs, 0, new ArrayList<>());
    }

    /**
     * 对 index 上的元素进行抉择：要 或 不要
     *
     * 省空间
     * @param chs
     * @param index
     */
    public static void choiceIndexCharPlus(char[] chs, int index) {
        if (index == chs.length) {
            System.out.println(String.valueOf(chs));
            return;
        }
        // 要 chs[index]
        choiceIndexCharPlus(chs, index + 1);
        char tmp = chs[index];

        // 不要 chs[index]
        chs[index] = 0;
        choiceIndexCharPlus(chs, index + 1);

        // 还原
        chs[index] = tmp;
    }

    /**
     * 对 index 上的元素进行抉择：要 或 不要
     * @param chs
     * @param index
     * @param res
     */
    public static void choiceIndexChar(char[] chs, int index, List<Character> res) {
        if (index == chs.length) {
            printList(res);
            return;
        }

        // 要 chs[index]
        List<Character> resKeep = copyList(res);
        resKeep.add(chs[index]);
        choiceIndexChar(chs, index + 1, resKeep);

        // 不要 chs[index]
        List<Character> resExclude = copyList(res);
        resKeep.add(chs[index]);
        choiceIndexChar(chs, index + 1, resExclude);
    }

    public static void printList(List<Character> res) {
        res.stream().forEach(e -> System.out.print(e));
        System.out.println();
    }

    public static List<Character> copyList(List<Character> objList) {
        List<Character> dest = new ArrayList<>(objList.size());
        dest.addAll(objList);
        return dest;
    }
}
